package cn.pugle.oj.leetcode;

import cn.pugle.oj.catalog.Greedy;

import java.util.Arrays;

/**
 * 使用最少步数
 * see 55
 * 比上一个快一些,
 * 这写法用个数组, 就像是动规了, 不是最优解法
 *
 * @author tzp
 * @since 2020/10/17
 */
public class LC45_1 implements Greedy {
    public int jump(int[] nums) {
        if (nums.length <= 1) return 0;
        int[] minSteps = new int[nums.length];
        int lastOneStepIndex = nums.length - 1;
        for (int i = nums.length - 2; i >= 0; i--) {
            if (nums[i] + i >= nums.length - 1) {
                minSteps[i] = 1;
                lastOneStepIndex = i;
            } else if (nums[i] + i >= lastOneStepIndex) {
                minSteps[i] = 2;
            } else {
                int minStep = Integer.MAX_VALUE;
                for (int j = nums[i]; j >= 1; j--) {
                    minStep = Math.min(minStep, minSteps[i + j]);
                }
                minSteps[i] = minStep == Integer.MAX_VALUE ? Integer.MAX_VALUE : 1 + minStep;
            }
        }
        System.out.println(Arrays.toString(minSteps));
        return minSteps[0];
    }

    public static void main(String[] args) {
        System.out.println(new LC45_1().jump(new int[]{4, 3, 1, 1, 1, 4}));
    }
}
